package Example_practice02;

import java.util.Scanner;

public class TriangleMaxSum {
    public static void main(String[] args){
        System.out.println("请输入三角形的高");
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[][] dp=new int[n][n];
        int[][] triangle=new int[n][n];

        System.out.println("请输入三角形的数据");

        //输入数学三角形
        for (int i=0;i<n;i++){
            for (int j=0;j<=i;j++){
                triangle[i][j]=scanner.nextInt();
            }
        }

        //初始化dp数组最后一行
        for (int i=n-1;i>=0;i--){
            dp[n-1][i]=triangle[n-1][i];
        }

        //自底向上求最大路径和
        for (int i=n-2;i>=0;i--){
            for (int j=0;j<=i;j++){
                dp[i][j]=Math.max(dp[i+1][j],dp[i+1][j+1]+triangle[i][j]);
            }
        }

        //取到路径最大值
        int maxSum=dp[0][0];
        System.out.println("路径最大值为"+maxSum);
    }

}
